The present invention relates in general to data processing systems and is particularly directed to a static dataflow computer architecture communications within which are effected through associative processing.
1. Field of the Invention
In static dataflow computer architectures, program execution is typically controlled by tokens, with directed information packets providing communication and synchronization among data execution control structures, or templates. Unfortunately, the amount of serial, temporal overhead required for a token-based processor to perform a single operation and the number of memory accesses per operation have effectively prevented static data flow computers from being employed for practical parallel data processing.
2. Summary of the Invention
In accordance with the present invention, the substantial temporal overhead and memory bandwidth requirements of token-based static data flow computer architectures are substantially reduced by replacing token-based processor communications with associative processing, similar to that used for associative memories, through which plural data execution control structures, or templates, of the system are interconnected with one another and with the data processing resources of the system, so that they may monitor and respond to operations carried out with respect to all other components of the system simultaneously, thereby increasing data processing execution speed and enhancing the efficient use of system memory.
For this purpose, in accordance with a first embodiment of the present invention involving a single processing node architecture, the static dataflow data processing system includes a functional computation unit, in which data processing operations are controllably executed, a template storage and control unit, and a pair of communication channels through which the functional computation unit and the template storage and control unit communicate with one another. The template storage and control mechanism controls the supply of data to be processed by the functional computation unit and includes memory for storing a plurality of templates. The template storage and control unit assembles data processing messages for application to a first of the communication channels for controlling the execution of a data processing operation by the functional computation unit. Each message contains first information representative of the identification of that template (its address) to which the result of the data processing operation is to be returned (via the second communication channel and stored in a return buffer within that template dedicated for the purpose), second information (an opcode) representative of the data processing operation to be performed by the functional computation unit, and third information representative of the data (either the data directly or the address of the template that contains the data) to be processed by the functional computation unit. Each template also stores the status of a data processing execution cycle. In accordance with the associative architecture of the present invention, each template is coupled to and continuously monitors the first and second communications channels for the presence of its address having been asserted thereon and, in response to detecting the presence of its address, controllably interfacing prescribed information associated with the execution of a data processing operation with respect to the first and second communication channels.
Each template monitors the first communications channel and asserts the contents of its return buffer onto the first communications channel in response to recognizing its address, so that the data stored in the return buffer may be employed as an operand for the execution of a data processing operation by the functional computation unit. In its status entry a template contains acknowledgement information representative of whether any other template requires the use of the contents of the return buffer. The status entry also includes operand availability information indicating whether the result entry of another template, whose address is defined by the contents of a source address entry of that template, contains an operand required for the execution of a data processing operation defined in accordance with opcode entry of that same template.
Each template also contains a code indicating its readiness to "fire", i.e. to have a data processing message asserted onto the first communications channel, in accordance with the contents of the status entry, and includes means for indicating the readiness of the template to have a data processing message asserted on the first communications channel in response to the acknowledgement information being representative that no other template requires the use of the contents of the current result entry of that template as an operand, and that the operand availability information indicates that all operands required for the execution of a data processing operation defined in accordance with opcode are available.
The template storage and control unit includes means for clearing the contents of the acknowledgement and operand availability information within the status entry of the template in the course of causing a data processing message associated with that template to be asserted onto the first communications channel.
The second communications channel includes a data portion over which output data from the functional computation unit is conveyed and a result address portion over which the address of an output data recipient template is conveyed. Each template includes a comparator for comparing its operand source address entries with the contents of the address portion of the second communications channel and controllably causes the operand availability information of the status entry to indicate that an operand entry required for the execution of a data processing operation defined in accordance with an opcode entry of the respective template is available in the result entry of another template whose address matches one of the operand source address entries of the respective template.
The second communications channel also includes a result index portion for identifying one of the operand source entries of a template, and the comparator includes means for causing the operand availability information of the status entry to indicate that an operand entry required for the execution of a data processing operation defined in accordance with an opcode entry of that template is available in the result entry of another template whose address matches the operand source address entry of the respective template as identified by the result index portion.
The first communications channel includes a data portion over which operands are conveyed, an address portion over which the address of a selected template is conveyed, an opcode portion over which the opcode entry of a selected template is conveyed, and an intra template address link over which operand source addresses are conveyable among the templates of said storage unit. Each template includes means for comparing its address with the contents of the intra template address link and causing the contents of its result entry to be asserted onto the data portion of the first communications channel, in response to detecting a match between its address and the contents of the intra template address link.
A respective template includes means for controllably asserting its operand source addresses onto the intra template address link in the course of the assertion of a data processing message, and the second communications channel includes a data portion over which output data is conveyed and a result address portion over which the address of an output data recipient template is conveyed. A template also includes means for controllably causing the operand address asserting means to assert an operand source address onto the intra template address link in accordance with the contents of the address portion of the second communications channel. A selected operand source address is asserted onto the intra template address link in accordance with the contents of a prescribed (least significant bit) portion of the data portion of the second communications channel.
In accordance with a second embodiment of the present invention, the associative template-based data processing mechanism is applied to a larger, system level architecture, comprised of multiple nodes, each having its own dedicated functional computation unit and template storage facility, wherein operand and result data are exchanged among the nodes of the system. The nodes preferably form a mesh topology, in which each node is connected with and may communicate with some number, e.g. three, nearest neighbor nodes with which it shares data resources in the course of execution of its own data processing operations and also in the course of the execution of data processing operations by those neighboring nodes. Namely, within an individual node, a data processing operation defined by a template stored within that node is always executed by the functional computation unit within that node. However, the operands required for and the results of that execution may be shared by templates in nearest neighbor nodes. In order to effect this sharing of data resources, the architecture of each node is configured to provide an inter-node associative communication capability, similar to that of an individual node, for those aspects of a template which may depend upon or be necessary for the execution of a template in any of its neighboring nodes, by assigning associative communication control functions to dedicated storage and supervisory units within each node.
For this purpose, the multi-node configuration of the associative data processing architecture of the present invention comprises a plurality of data processing nodes each of which includes its own dedicated functional computation unit and a program execution control unit which contains a plurality of templates, each template comprising a plurality of entries, including an address for identifying that template, a plurality of operand source entries for specifying the addresses of operands to be employed in the execution of a data processing operation associated with that template, and the status of the template with respect to its associated data processing operation. Each node also contains an opcode store, coupled to the program execution control unit, for storing a plurality of opcodes respectively associated with the plurality of templates, and an opcode which defines a data processing operation to be performed by the functional computation unit. Also included within each node is an operand store, which is coupled to the program execution control unit, for storing a plurality of result entries in which output data produced by the functional computation unit as a result of its execution of a data processing operation requested by a template are stored.
Assembly of a data processing message is carried out by an operation packet builder, which is coupled to the program execution control unit, the opcode store and the operand store. The operation packet builder assembles a plurality of data processing messages to be forwarded to the functional computation unit for execution, a respective data processing message including the identification of a respective template, the contents of respective result entries identified by operand source addresses of said respective template, and the opcode associated with said respective template.
A first communications channel is coupled between the operation packet builder and the functional computation unit for conveying data processing request messages between the packet builder and the functional computation unit. A second communications channel is coupled between the functional computation unit, the program execution control unit, storage unit and the operand store, for conveying output data from the functional computation unit to the operand store and the identification of the template for which a data processing request message has been processed by the functional computation unit to the program execution control unit.
A first internode communication channel is coupled to the second communication channel of each node, for coupling the identification of the template for which a data processing request message has been processed by its associated functional computation unit to the program execution control unit in each node. A second internode communication channel is coupled to the operand store, the operation packet builder, and the program execution control unit of each node, for enabling the operand addresses of a template stored within the program execution control unit of a node to be presented to the operand store of every other adjacent node, and for enabling operand values stored in any node to be presented to the operation packet builder of any node.
The status entry of a respective template includes operand availability information representative of whether the result entry of another template in any neighboring node, whose address is defined by the contents of a source address entry of the template, contains an operand required for the execution of a data processing operation defined in accordance with opcode entry of the template.
The second communications channel includes a data portion over which output data from the functional computation unit is conveyed and a result address portion over which the address of said respective template is conveyed, and the program execution control unit includes a comparator for comparing the operand source entries of the template with the contents of the address portion of the second communications channel and causes the operand availability information of the status entry to indicate that an operand required for the execution of a data processing operation defined in accordance with an opcode associated with the template is available in the operand store of that node which contains the template whose identification matches one of the operand source address entries of the template.
The second communications channel further includes a result index portion for identifying one of the operand entries of a template and the comparator outputs a signal which causes the operand availability information of the status entry to indicate that an operand entry required for the execution of a data processing operation defined in accordance with an opcode entry of the template is available in the operand store of a node containing the template whose address matches the operand source address entry of the template as identified by the result index portion.